package 算法.leetcode.offer;

/**
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 *
 *  
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 *  
 *
 * 示例 1:
 *
 * 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
 * 输出: 2
 *
 * @author lchenglong
 * @date 2022/3/19
 */
public class Offer39 {

    public static void main(String[] args) {
        Offer39 instance = new Offer39();
        int i = instance.majorityElement(new int[]{1,2,2,4,2});
        System.out.println(i);
    }
    public int majorityElement(int[] nums) {
        int votes = 0,x=0;
        for (int i=0;i<nums.length;i++){
            if (votes == 0)x = nums[i];
            votes += nums[i]==x?1:-1;
        }
        return x;
    }
}
